#include "LinkList.h"
#include <iostream>
LinkList::LinkList():head(new Node),size(0)
{
    head->data = 0;
    head->next = nullptr;

    m_tail = head;
}

LinkList::~LinkList()
{
    while(head != nullptr)
    {
        Node*nextNode = head->next;
        delete head;
        head = nextNode;
    }
}

inline LinkList::Node* LinkList::CreateNode(ElementType element)
{
    Node *newNode = new Node;
    newNode->data = element;
    newNode->next = nullptr;
    return newNode;
}

void LinkList::InsertTail(ElementType element)
{
#if 0
    Node *travelPoint = head;
    while(travelPoint->next != nullptr) //有下一个节点
        travelPoint = travelPoint->next;
    travelPoint->next = CreateNode(element);
    size++;
#endif
    InsertByIndex(this->size,element);
}

void LinkList::InsertHead(ElementType element)
{   
#if 0
    Node *newNode = CreateNode(element);
    newNode->next = head->next;
    head->next = newNode;
    size++;
#endif
    InsertByIndex(0,element);
}

void LinkList::InsertByIndex(int index, ElementType element)
{   
    Node* travelPoint = head;
    Node *newNode = CreateNode(element);
    bool flag = false;
    if(index == this->size)
    {
        /*需要改尾指针*/
        travelPoint = m_tail;

        flag = true;
    }
    else
    {
        for(int i = 0;i < index;i++) //因为有头节点的存在所以取i < index
        {
            travelPoint = travelPoint->next;
        }
    }
    newNode->next = travelPoint->next;
    travelPoint->next = newNode;
    if(flag = true)
    {
        m_tail = newNode; 
    }
    size++;
}

void LinkList::RemoveByIndex(int index)
{
    Node* travelPoint = head;
    bool flag = false;
    if(index == this->size -1)
    {
        //只有这种情况才需要改尾指针
        flag = true;
    }
    for(int i = 0; i < index;i++)
    {
        travelPoint = travelPoint->next;
    }

    Node*freeNode = travelPoint->next;
    travelPoint->next = freeNode->next;
    delete freeNode;
    if(flag == true)
    {
        m_tail = travelPoint;
    }
    /*更新链表元素个数*/
    size--;
}

void LinkList::RemoveByElement(ElementType element)
{
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(travelPoint->next->data == element)
        {
            Node*freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            delete freeNode;
            size--;
        }
        else
            travelPoint = travelPoint->next;
    }
}

void LinkList::UpdateByIndex(int index, ElementType newValue)
{
    Node *travelPoint = head;
    for(int i = 0;i <= index;i++)
        travelPoint = travelPoint->next;
    travelPoint->data = newValue;
}

void LinkList::UpdateByElement(ElementType oldValue, ElementType newValue)
{
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(travelPoint->next->data == oldValue)
            travelPoint->next->data = newValue;
        travelPoint = travelPoint->next;   
    }
}

ElementType &LinkList::operator[](int index)
{
    Node *travelPoint = head;
    for(int i = 0;i <= index;i++)
    travelPoint = travelPoint->next;
    return travelPoint->data;
}

void LinkList::BubbleSort()
{
    for(int i = 0;i < size-1;i++)
    {   
        Node * travelPoint = head;//每次扫描链表回到起始点
        for(int j = 0;j < size-i-1;j++)
        {   
            if(travelPoint->next->data > travelPoint->next->next->data)
            {
                Node *Prev = travelPoint->next;
                Node *Next = Prev->next;

                Prev->next = Next->next; 
                Next->next = Prev;
                travelPoint->next = Next;
            }
            travelPoint = travelPoint->next;
        }
    }
}

void LinkList::FastSort()
{
    FastSort(head->next,nullptr); 
}

LinkList LinkList::Merge(const LinkList &l)
{   
    LinkList result;

    Node *p1 = this->head->next;
    Node *p2 = l.head->next;
    while(p1 !=nullptr && p2 !=nullptr)
    {
        if(p1->data < p2->data)
        {
            result.InsertTail(p1->data);
            p1 = p1->next;
        }
        else
        {
            result.InsertTail(p2->data);
            p2 = p2->next;
        }
        
    }
        while(p1)
        {
            result.InsertTail(p1->data);
            p1 = p1->next;
        }

        while(p2)
        {
            result.InsertTail(p2->data);
            p2 = p2->next;
        }

        return result;
}

void LinkList::Reserve()
{
    Node * prev = nullptr;
    Node * cur =  head->next;
    Node * Next = cur->next;
    while(Next != nullptr)
    {
        cur->next = prev;
        prev = cur;
        cur = Next;
        Next = cur->next;
    }
    cur->next = prev;
    head->next = cur;
}

LinkList::Node* LinkList::Reserve2(Node *node)
{   
    //
    if(node->next == nullptr)
    {
        return node;
    }
    else
    {
        Node* newHeader = Reserve2(node->next);
        node->next->next = node;
        node->next = nullptr;
        return newHeader;
    }
}

void LinkList::Reserve2()
{
    head->next = Reserve2(head->next);
}

void LinkList::show()
{   
    Node * travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        std::cout<<travelPoint->next->data<<" ";
        travelPoint = travelPoint->next;
    }
    std::cout<<std::endl;
}

LinkList::Node *LinkList::Getend()
{   
    Node * travelPoint = head;
    while(travelPoint->next != nullptr)
        travelPoint = travelPoint->next;
    return travelPoint;
}

void LinkList::FastSort(Node *start, Node *end)
{
    if(start == end)
        return;

    Node* temp = start; //基准值
    Node* p1 = start; //left
    Node* p2 = p1->next; //right

    while(p2 != end)
    {   
        //比基准值小
        if(p2->data < temp->data)
        {
            p1 = p1->next;
            std::swap(p1->data,p2->data);
        }
        p2 = p2->next;
    }
    std::swap(p1->data,temp->data); //将基准值和p1的值互换

    FastSort(start,p1);
    FastSort(p1->next,end);
}
 int LinkList:: getSize()
 {
    return size;
 }